/**
 * 
 */
package com.gwcloud.leetcode.hot100;

import com.gwcloud.leetcode.common.datastructure.ListNode;

/**
 * @ClassName   : Leetcode019 
 * @author      : ganwei 
 * @date        : 2020年5月4日
 * @Description : Leetcode019 删除链表的倒数第N个节点
 */
public class Leetcode0019 {
	/**
	 * -解题思路，扫描两遍
	 */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head.next == null){
            return null;
        }
    	ListNode index = head;
    	int listlength = 0;
    	while(index != null){
    		listlength++;
    		index = index.next;
    	}
    	ListNode indexl = null;
    	index = head;
    	for(int i = 0 ; i < (listlength-n); i++){
    		indexl = index;
    		index = index.next;
    	}
        if(indexl == null){
            head = head.next;
            index.next = null;
        }else{
            indexl.next = index.next;
        }
    	
    	return head;
    }
    
    /**
     * 解题思路，遍历一遍,快慢指针,先让一个指针移动n
     */
    public ListNode removeNthFromEnd_1(ListNode head, int n){
    	ListNode pre = new ListNode(0);
    	pre.next = head;
    	ListNode start = pre, end = pre;
    	while(n != 0){
    		n--;
    		start = start.next;
    	}
    	
    	while(start.next != null){
    		start = start.next;
    		end = end.next;
    	}
    	end.next = end.next.next;
    	return pre.next;
    }
    public static void main(String[] args){
    	
    }
}
